package top.zhanglingxi.algorithms;

import cn.hutool.core.date.DateUtil;
import cn.hutool.core.date.TimeInterval;
import lombok.extern.slf4j.Slf4j;
import top.zhanglingxi.enums.PointEnum;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;

/**
 * 广度优先算法
 *
 * @author ZWX
 */
@Slf4j
public class BFS implements ICalcShortestPath {

    /**
     * 步item
     */
    static class StepItem {

        /**
         * 路径长度
         */
        int distance;

        /**
         * 坐标点
         */
        Point point;

        /**
         * 前驱步
         */
        StepItem prevStep;

        public StepItem(int distance, Point point, StepItem prevStep) {
            this.distance = distance;
            this.point = point;
            this.prevStep = prevStep;
        }

        @Override
        public String toString() {
            return "distance =" + distance + ", point x =" + point.getX() + ", point y =" + point.getY();
        }
    }

    @Override
    public ShortestPath getShortestPath(Labyrinth labyrinth) {

        log.info("===== BFS开始计算迷宫最短路径 =====");
        TimeInterval timer = DateUtil.timer();

        // 最短路径结果
        ShortestPath shortestPath = new ShortestPath();

        // 迷宫长度
        int length = labyrinth.getLength();
        // 迷宫宽度
        int width = labyrinth.getWidth();
        // 点数组
        Point[][] points = labyrinth.getPoints();
        // 起点
        Point start = labyrinth.getStart();
        // 终点
        Point end = labyrinth.getEnd();
        // 初始化队列和已访问集合
        Queue<StepItem> stepQueue = new LinkedList<>();
        boolean[][] visited = new boolean[length][width];

        // 将起点加入队列
        StepItem startStep = new StepItem(0, start, null);
        stepQueue.add(startStep);
        visited[start.getX()][start.getY()] = true;

        while (!stepQueue.isEmpty()) {
            StepItem currentStep = stepQueue.poll();
            if (currentStep.point.getType() == PointEnum.GREEN) {
                shortestPath.setDistance(currentStep.distance);
                shortestPath.setPoints(reconstructPath(currentStep));
                break;
            }
            exploreNeighbors(currentStep, stepQueue, visited, points);
        }
        log.info("===== BFS计算迷宫最短路径完成 =====");
        //花费毫秒数
        long interval = timer.interval();
        shortestPath.setTime(interval);
        return shortestPath;
    }

    /**
     * 用于从 StepItem 回溯并重建最短路径。
     * @param step 待回溯步骤
     * @return 最短路径
     */
    private Point[] reconstructPath(StepItem step) {
        LinkedList<Point> path = new LinkedList<>();
        while (step != null) {
            path.addFirst(step.point);
            step = step.prevStep;
        }
        return path.toArray(new Point[0]);
    }

    /**
     * 用于探索当前点的邻居节点，并检查它们是否可以访问。
     * @param currentStep 当前步骤
     * @param queue 待访问队列
     * @param visited 已访问集合
     * @param points 迷宫
     */
    private void exploreNeighbors(StepItem currentStep, Queue<StepItem> queue, boolean[][] visited,
                                  Point[][] points) {
        int[] dx = {0, 1, 0, -1};
        int[] dy = {1, 0, -1, 0};

        for (int i = 0; i < 4; i++) {
            int newX = currentStep.point.getX() + dx[i];
            int newY = currentStep.point.getY() + dy[i];

            if (newX >= 0 && newX < points.length && newY >= 0 && newY < points[0].length &&
                    !visited[newX][newY] && points[newX][newY].getType() != PointEnum.GREY) {
                queue.add(new StepItem(currentStep.distance + 1, points[newX][newY], currentStep));
                visited[newX][newY] = true;
            }
        }
    }
}
